\begin{definition}
	pokrytí maximálního bloku active equality treeS
\end{definition}

\begin{theorem}\label{theorem:saeq}
	Let $\sigma$ is feasible schedule. If each maximum block in $\sigma$ is on time and can be covered by a spanning active equality tree, then the schedule is optimal\footnote{v původním článku PERT je tato věta definována jako ekvivalence, ale nám stačí implikace}.
\end{theorem}
\begin{proof}
Důkaz provedeme sporem. Nechť rozvrh $\sigma$ není optimální, pak ukážeme, že existuje maximální blok, který nelze pokrýt spanning active equality tree nebo není on time.

Nejprve ukážeme, že pokud existuje maximální blok $B$, který není on time, pak rozvrh $\sigma$ není optimální: Pokud není $B$ on time, pak je buď strictly early nebo strictly late. Předpokládejme, že $B$ je strictly early (případ pro strictly late lze dokázat analogicky). Tzn. že existuje $t>\sigma(B)$, tak že $c_{B,\sigma}(t) < c_{B,\sigma}(\sigma(B))$. Pokud se bloku B "nedotýká" žádný jiný blok, tedy $\forall i\notin B$ a $\forall (i,j)$ (resp. $(j,i)$), kde $j\in B$ platí $\sigma(i)+p_i\neq \sigma(j)$ (resp. $\sigma(j)+p_j\neq \sigma(i)$).

Blok $B$ je maximální. Z definice maximálního bloku vyplývá, že existuje $\epsilon>0$ takové, že pro nový start $\widetilde{\sigma}(B) = \sigma(B) + \epsilon$ se množina aktivit v bloku $B$ nezmění. Pokud takové $\epsilon$ neexistuje, znamená to to, že se nějaká aktivita $\notin B$ spojená precedencí s blokem $B$ dotýkala bloku $B$. 

Tudíž rozvrh $\sigma$ nebyl optimální. 




Nyní budeme předpokládat neoptimální rozvrh $\sigma$, ve kterém jsou všechny maximální bloky on time, a ukážeme, že nějaký z nich nelze pokrýt spanning active equality tree. Protože rozvrh $\sigma$ není optimální, pak v něm existuje nějaký maximální blok $B$, který není optimální. Uvažujme nyní rozvrh $\sigma_B=\sigma$ bloku $B$ zcela samostatně. Víme, že rozvrh $\sigma_B$ není optimální a zároveň blok $B$ je on time. Protože je blok $B$ on time, nelze získat lepší rozvrh posunem celého bloku $B$. Tudíž v optimálním rozvrhu $\sigma_B^*$ nemůže být blok $B$ maximální, ale existuje rozdělení bloku $B$ na více bloků $B_1, B_2,\ldots$ Je zřejmé, že pro nějaký blok $B_k$ platí $\sigma_B(B_k) \neq \sigma_B^*(B_k)$. Uvažujme všechny precedence $(i,j)$ takové, že $i\in B \wedge j\in B \wedge ((i\in B_k \wedge j\notin B_k) \vee (i\notin B_k \wedge j\in B_k$)). Žádná z těchto precedencí nemohla být v rozvrhu $\sigma_B$ aktivní, protože se vyplatilo rozdělit blok $B$ na dvě části (tj. $B_k$ a $B\backslash B_k$), které jsou v $\sigma^*$ optimální (viz. definice active arc). Tudíž blok $B$ nebylo možné pokrýt spanning active equality tree. (tvrzení o tom, že precedence nebyly aktivní bude chtít ještě promyslet a podrobněji rozepsat, ale věřím, že to takto nějak musí fungovat)
\end{proof}

\section{Algorithm}
\emph{toto je jen velmi strohý nástřel}\\
Nechť je dána libovolná instance PERTCONVGD. V první fázi ověříme, zda existuje přípustný rozvrh (viz Roman Barták). V druhé fázi sestavíme výchozí rozvrh $\sigma^1$, ve kterém umístíme všechny aktivity z $\mathcal{O}$ do svého optima bez ohledu na precedence: Pro každou aktivitu $k\in \mathcal{O}$ nastavíme $\sigma^1(k) = argmin_t( c_k(t))$. Rozvrh $\sigma^1$ obsahuje právě $n$ maximálních bloků (každá aktivita tvoří jeden blok). Každý z těchto bloků je on time, tudíž na základě věty \ref{theorem:saeq} je rozvrh $\sigma^1$ optimální. Rozvrh $\sigma^1$ je zároveň přípustný, protože neobsahuje žádné precedence, které by mohly být porušené. Očíslujme precedence od jedné dále (pořadí nehraje roli). V další fázi budeme iterativně vkládat do rozvrhu jednotlivé precedence $p\in \{1,2 \ldots\}$ a v každé iteraci upravíme rozvrh tak, abychom získali přípustný optimální rozvrh $\sigma^{p+1}$. Pokud je ihned po vložení precedence $p$ rozvrh $\sigma^{p+1}$ rovnou přípustný, můžeme pokračovat v další iteraci s precedencí $p+1$ (rozvrh $\sigma^p$ byl optimální, proto i $\sigma^{p+1}$ je stále optimální (nehýbalo se s žádnou aktivitou)). Pokud rozvrh $\sigma^{p+1}$ není přípustný, musíme ho přípustný a optimální udělat. Nechť $p \equiv (i,j)$. Označme $B_i$ (resp. $B_j$) jako maximální blok obsahující aktivitu $i$ (resp. $j$). Precedence $p$ může být porušena ze dvou důvodů: 
\begin{itemize}
	\item buď $\sigma^p(i) + p_i > \sigma^p(j)$. V tomto případě se aktivity překrývají. Můžeme začít posouvat blok $B_j$ doprava na pozici $\sigma(B_j) = \sigma^p(i) + p_i$ (za použití událostí $E_1', E_2'$ a $E_3'$ analogicky inverzních k událostem $E_1, E_2$ a $E_3$ z původního článku). Nyní máme rozvrh který je přípustný, ale není optimální.
	\item nebo $\sigma^p(i) + p_i + \distij < \sigma^p(j)$. V tomto případě $i$ a $j$ moc daleko od sebe. Můžeme začít posouvat blok $B_i$ doprava na pozici $\sigma(B_i) = \sigma^p(j) - \distij - p_i$ (opět za použití událostí $E_1', E_2'$ a $E_3'$). Nyní máme rozvrh který je přípustný, ale není optimální.
\end{itemize}  

V obou případech vnikl nový maximální blok obsahující obě aktivity $i$ a $j$, který není optimální (zbytek bloků v rozvrhu je optimální). Blok obsahující aktivity $i$ a $j$ lze pak začít posouvat doleva (resp. doprava) za použití událostí $E_1, E_2$ a $E_3$ (resp. $E_1', E_2'$ a $E_3'$). Takto získáme optimální rozvrh (všechny bloky jsou on time a lze je pokrýt spanning active equality tree - to by mělo být zaručeno způsobem posouvání aktivit za pomoci událostí $E_{1,\ldots,3}$ a $E'_{1,\ldots,3}$). 

Třeba by šlo posouvat bloky nějak rozumněji, aby byl algoritmus o trochu rychlejší.
}
















\section{Optimalita}
Oproti původnímu článku vynechávám definici bloku a maximálního bloku. Místo toho nadefinuji kostru nejen přes maximální bloky ale přes všechny aktivity. Na této kostře pak definuji pojem aktivní hrana - v mé definici je oproti původnímu článku aktivní hrana ta, kde dochází ke skutečnému ``pnutí``. Dále z této kostry vyjmu všechny neaktivní hrany, čímž se mi kostra rozpadne na jednotlivé komponenty, které ve většině případů odpovídají maximálním blokům z původního článku.

Následuje jen formální definice pro $\eqt_i$ a $\eqt_j$ označující dvě komponenty vzniklé odstraněním hrany $(i,j)$ z kostry $\eqt$.
\begin{definition}
  Nechť $\eqt$ je kosta libovolného souvislého grafu $G$. Nechť $(i,j)$ je hrana z $\eqt$. Pak označíme $\eqt_i$ (resp. $\eqt_j$) komponentu obsahující vrchol $i$ (resp. $j$) vzniklou odstrarněním hrany $(i,j)$ z $\eqt$.
\end{definition}

Další definice uvažuje $B$ jako libovolnou množinu aktivit. V původním článku musel být graf indukovaný touto množinou souvislý.
\begin{definition}
  Nechť $(G,p,c)$ je instance PERTCONVD. Nechť $B\cup \mathcal{O}$. The start time $\sigma(B)$ of $B$ is $\min_{i\in B} \sigma(i)$. The cost function $c_{B,\sigma}(t) = \sum_{i\in B}c_i (t + \sigma(i) - \sigma(B))$. Řekneme že $B$ je \emph{early} pokud $\sigma{B}=0$ nebo pokud pro libovolné $t\in[0,\sigma(B)], c_{B,\sigma}(t) \geq c_{B,\sigma}(\sigma(B))$ ($B$ se nevyplatí šoupnout doleva). Blok $B$ označíme jako \emph{late} pokud pro libovolné $t\geq \sigma(B), c_{B, \sigma}(t) \geq c_{B, \sigma}(\sigma(B))$ ($B$ se nevyplatí šoupnout doprava). Řekneme, že $B$ je \emph{strictly early} (resp. \emph{strictly late}) pokud není late (resp. early). ($B$ se vyplatí šoupnout doprava (resp. doleva)). $B$ je \emph{on time} pokud je zároveň early i late ($B$ je ve své nejlepší pozici a nevyplatí se ho šoupnout ani vpravo ani vlevo).
\end{definition}
Protože jednotlivé funkce $c_i$ jsou konvexní, pak i $c_{B,\sigma}(t)=\sum_{i\in B}c_i (t + \sigma(i) - \sigma(B))$ je konvexní.


\begin{definition}
Nechť $\sigma$ je přípustný rozvrh na $G$. Nechť $\eqt$ je libovolná kostra grafu $G$. Pak řekneme, že hrana $(i,j)\in \eqt$ je \emph{aktivní}, pokud:
\begin{itemize}
 \item $p_i+\sigma(i)=\sigma(j)$, 
\end{itemize}
asdf
